#include <iostream>
#include <vector>
#include <stack>
using namespace std;

/*
 *这道题没啥难度，就是单调栈的一次应用而已。
 *既然我们不能一次性确定出最佳答案在哪里，那么我们至少可以放宽一定的条件那就是求出
 *每一个点以其为最低点的话能“框”出多大的矩形。
 */

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n=heights.size();
        stack<int> index;
        int area=0;
        for(int i=0;i<heights.size();i++){
            if(index.empty()||heights[index.top()]<heights[i]) index.push(i);
            else{
                while(!index.empty()&&heights[index.top()]>=heights[i]){
                    int tmp=index.top();
                    index.pop();
                    int length=0;
                    if(index.empty()) length=i;
                    else length=i-index.top()-1;
                    area=max(area,length*heights[tmp]);
                }
                index.push(i);
            }
        }
        while(!index.empty()){
            int tmp=index.top();
            index.pop();
            int length=0;
            if(index.empty()) length=n;
            else length=n-index.top()-1;
            area=max(area,length*heights[tmp]);
        }
        return area;
    }
};


int main(int argc, char *argv[])
{
	
	return 0;
}

